home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / digital marsC compier / dm / stl / stl_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-08  |  9.9 KB  |  298 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  * Copyright (c) 1997
  15.  * Silicon Graphics Computer Systems, Inc.
  16.  *
  17.  * Permission to use, copy, modify, distribute and sell this software
  18.  * and its documentation for any purpose is hereby granted without fee,
  19.  * provided that the above copyright notice appear in all copies and
  20.  * that both that copyright notice and this permission notice appear
  21.  * in supporting documentation.  Silicon Graphics makes no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied warranty.
  24.  */
  25.  
  26. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29.  
  30. #ifndef __SGI_STL_INTERNAL_HEAP_H
  31. #define __SGI_STL_INTERNAL_HEAP_H
  32.  
  33. __STL_BEGIN_NAMESPACE
  34.  
  35. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  36. #pragma set woff 1209
  37. #endif
  38.  
  39. // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  40.  
  41. template <class _RandomAccessIterator, class _Distance, class _Tp>
  42. void 
  43. __push_heap(_RandomAccessIterator __first,
  44.             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  45. {
  46.   _Distance __parent = (__holeIndex - 1) / 2;
  47.   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  48.     *(__first + __holeIndex) = *(__first + __parent);
  49.     __holeIndex = __parent;
  50.     __parent = (__holeIndex - 1) / 2;
  51.   }    
  52.   *(__first + __holeIndex) = __value;
  53. }
  54.  
  55. template <class _RandomAccessIterator, class _Distance, class _Tp>
  56. inline void 
  57. __push_heap_aux(_RandomAccessIterator __first,
  58.                 _RandomAccessIterator __last, _Distance*, _Tp*)
  59. {
  60.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
  61.               _Tp(*(__last - 1)));
  62. }
  63.  
  64. template <class _RandomAccessIterator>
  65. inline void 
  66. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  67. {
  68.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  69.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
  70.                  _LessThanComparable);
  71.   __push_heap_aux(__first, __last,
  72.                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
  73. }
  74.  
  75. template <class _RandomAccessIterator, class _Distance, class _Tp, 
  76.           class _Compare>
  77. void
  78. __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  79.             _Distance __topIndex, _Tp __value, _Compare __comp)
  80. {
  81.   _Distance __parent = (__holeIndex - 1) / 2;
  82.   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
  83.     *(__first + __holeIndex) = *(__first + __parent);
  84.     __holeIndex = __parent;
  85.     __parent = (__holeIndex - 1) / 2;
  86.   }
  87.   *(__first + __holeIndex) = __value;
  88. }
  89.  
  90. template <class _RandomAccessIterator, class _Compare,
  91.           class _Distance, class _Tp>
  92. inline void 
  93. __push_heap_aux(_RandomAccessIterator __first,
  94.                 _RandomAccessIterator __last, _Compare __comp,
  95.                 _Distance*, _Tp*) 
  96. {
  97.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
  98.               _Tp(*(__last - 1)), __comp);
  99. }
  100.  
  101. template <class _RandomAccessIterator, class _Compare>
  102. inline void 
  103. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  104.           _Compare __comp)
  105. {
  106.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  107.   __push_heap_aux(__first, __last, __comp,
  108.                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
  109. }
  110.  
  111. template <class _RandomAccessIterator, class _Distance, class _Tp>
  112. void 
  113. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  114.               _Distance __len, _Tp __value)
  115. {
  116.   _Distance __topIndex = __holeIndex;
  117.   _Distance __secondChild = 2 * __holeIndex + 2;
  118.   while (__secondChild < __len) {
  119.     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
  120.       __secondChild--;
  121.     *(__first + __holeIndex) = *(__first + __secondChild);
  122.     __holeIndex = __secondChild;
  123.     __secondChild = 2 * (__secondChild + 1);
  124.   }
  125.   if (__secondChild == __len) {
  126.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  127.     __holeIndex = __secondChild - 1;
  128.   }
  129.   __push_heap(__first, __holeIndex, __topIndex, __value);
  130. }
  131.  
  132. template <class _RandomAccessIterator, class _Tp, class _Distance>
  133. inline void 
  134. __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  135.            _RandomAccessIterator __result, _Tp __value, _Distance*)
  136. {
  137.   *__result = *__first;
  138.   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
  139. }
  140.  
  141. template <class _RandomAccessIterator, class _Tp>
  142. inline void 
  143. __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
  144.                _Tp*)
  145. {
  146.   __pop_heap(__first, __last - 1, __last - 1, 
  147.              _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
  148. }
  149.  
  150. template <class _RandomAccessIterator>
  151. inline void pop_heap(_RandomAccessIterator __first, 
  152.                      _RandomAccessIterator __last)
  153. {
  154.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  155.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
  156.                  _LessThanComparable);
  157.   __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
  158. }
  159.  
  160. template <class _RandomAccessIterator, class _Distance,
  161.           class _Tp, class _Compare>
  162. void
  163. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  164.               _Distance __len, _Tp __value, _Compare __comp)
  165. {
  166.   _Distance __topIndex = __holeIndex;
  167.   _Distance __secondChild = 2 * __holeIndex + 2;
  168.   while (__secondChild < __len) {
  169.     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
  170.       __secondChild--;
  171.     *(__first + __holeIndex) = *(__first + __secondChild);
  172.     __holeIndex = __secondChild;
  173.     __secondChild = 2 * (__secondChild + 1);
  174.   }
  175.   if (__secondChild == __len) {
  176.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  177.     __holeIndex = __secondChild - 1;
  178.   }
  179.   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
  180. }
  181.  
  182. template <class _RandomAccessIterator, class _Tp, class _Compare, 
  183.           class _Distance>
  184. inline void 
  185. __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  186.            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
  187.            _Distance*)
  188. {
  189.   *__result = *__first;
  190.   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
  191.                 __value, __comp);
  192. }
  193.  
  194. template <class _RandomAccessIterator, class _Tp, class _Compare>
  195. inline void 
  196. __pop_heap_aux(_RandomAccessIterator __first,
  197.                _RandomAccessIterator __last, _Tp*, _Compare __comp)
  198. {
  199.   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
  200.              __DISTANCE_TYPE(__first));
  201. }
  202.  
  203. template <class _RandomAccessIterator, class _Compare>
  204. inline void 
  205. pop_heap(_RandomAccessIterator __first,
  206.          _RandomAccessIterator __last, _Compare __comp)
  207. {
  208.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  209.   __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
  210. }
  211.  
  212. template <class _RandomAccessIterator, class _Tp, class _Distance>
  213. void 
  214. __make_heap(_RandomAccessIterator __first,
  215.             _RandomAccessIterator __last, _Tp*, _Distance*)
  216. {
  217.   if (__last - __first < 2) return;
  218.   _Distance __len = __last - __first;
  219.   _Distance __parent = (__len - 2)/2;
  220.     
  221.   while (true) {
  222.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
  223.     if (__parent == 0) return;
  224.     __parent--;
  225.   }
  226. }
  227.  
  228. template <class _RandomAccessIterator>
  229. inline void 
  230. make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  231. {
  232.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  233.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
  234.                  _LessThanComparable);
  235.   __make_heap(__first, __last,
  236.               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
  237. }
  238.  
  239. template <class _RandomAccessIterator, class _Compare,
  240.           class _Tp, class _Distance>
  241. void
  242. __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  243.             _Compare __comp, _Tp*, _Distance*)
  244. {
  245.   if (__last - __first < 2) return;
  246.   _Distance __len = __last - __first;
  247.   _Distance __parent = (__len - 2)/2;
  248.     
  249.   while (true) {
  250.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
  251.                   __comp);
  252.     if (__parent == 0) return;
  253.     __parent--;
  254.   }
  255. }
  256.  
  257. template <class _RandomAccessIterator, class _Compare>
  258. inline void 
  259. make_heap(_RandomAccessIterator __first, 
  260.           _RandomAccessIterator __last, _Compare __comp)
  261. {
  262.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  263.   __make_heap(__first, __last, __comp,
  264.               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
  265. }
  266.  
  267. template <class _RandomAccessIterator>
  268. void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  269. {
  270.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  271.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
  272.                  _LessThanComparable);
  273.   while (__last - __first > 1)
  274.     pop_heap(__first, __last--);
  275. }
  276.  
  277. template <class _RandomAccessIterator, class _Compare>
  278. void 
  279. sort_heap(_RandomAccessIterator __first,
  280.           _RandomAccessIterator __last, _Compare __comp)
  281. {
  282.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  283.   while (__last - __first > 1)
  284.     pop_heap(__first, __last--, __comp);
  285. }
  286.  
  287. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  288. #pragma reset woff 1209
  289. #endif
  290.  
  291. __STL_END_NAMESPACE
  292.  
  293. #endif /* __SGI_STL_INTERNAL_HEAP_H */
  294.  
  295. // Local Variables:
  296. // mode:C++
  297. // End:
  298.